package primary.code02_Sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 快排 (不稳定)
 * 荷兰旗问题，三个，随机数作为标准
 * <p>
 * 时间复杂度 O(N*logN)
 * 空间复杂度（递归栈深度） O(logN)
 * 时间复杂度（常数项小） O(N*logN)  空间复杂度 O(logN)  不稳定
 */
public class Code05_QuickSort {

    private static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSortTest(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;
        int rand = l + (int) (Math.random() * (r - l + 1));
        int[] res = partition(arr, l, r, arr[rand]);
//        int[] res = partitionTest(arr, l, r, arr[rand]);
        quickSort(arr, l, res[0]);
        quickSort(arr, res[1], r);
    }

    /**
     * 以最后一个元素作为分组基准
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int[] partition(int[] arr, int l, int r, int num) {
        int index = l;
        int p1 = l - 1;
        int p2 = r + 1;
        while (index != p2) {
            if (arr[index] < num) {
                swap(arr, index++, ++p1);
            } else if (arr[index] == num) {
                index++;
            } else {
                swap(arr, index, --p2);
            }
        }
        return new int[]{p1, p2};
    }

    private static void quickSortTest(int[] arr, int l, int r) {
        if (arr == null || l >= r) {
            return;
        }
        int[] res = partitionTest(arr, l, r);
        quickSortTest(arr, l, res[0]);
        quickSortTest(arr, res[1], r);
    }

    private static int[] partitionTest(int[] arr, int l, int r) {
        int randomNum = arr[l + (int) (Math.random() * (r - l + 1))];
        int pl = l - 1;
        int pg = r + 1;
        int i = l;
        while (i < pg) {
            if (arr[i] < randomNum) {
                swap(arr, ++pl, i++);
            } else if (arr[i] > randomNum) {
                swap(arr, --pg, i);
            } else {
                i++;
            }
        }
        return new int[]{pl, pg};
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;//交换的两个值不能是同一内存空间
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
        int[] arr = {4, 57, 87, 23, 23, 1, 8, 57, 8, 1, 587, 89};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
